package 动态规划.另类的;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/1/4 10:57
 */
public class leetcode53最大子数组和 {
    /*
       这种动态规划 要注意 一下 ，最终解 并不是 递归 传入的 的初始 参数
      按照 往常的 习惯 都是 f(0)
      但是 这种 dp  就不太一样 ,一次 没办法 求出,再遍历一遍不行了
     */


    /*
     暴力递归
     递归含义的解释：  y = f(index) 表示的 是 以 index 开头所有 连续子数组的 最大值
    而  y = f(index + 1)  与 f(index) 是存在 一定的关系的 (这个关系 一画图 就明白了)
    所以 f(index) = max(f(index + 1) + nums[index], nums[index]) ,这个 nums[index] 这个 区间 是 index + 开头的 不包括的子数组
    所以 需要比较 这两个的 大小,才能决定 当前的 f(index)
    -------
    下面的递归 的问题 : 只能求出 f(index) (index 的范围 0 ~ len )
    但是 最优解 是 不 一定 是 f(0),而是 f(index) index = 0 ~ len
    但是 通过加入 dp[] 缓存表 可以 把 每一个 f(index) 都求出来
    然后 在遍历 dp[] 表 找出最大值 就是最终的结果
     */
    public int recursion(int index,int []nums){
        if(index == nums.length){
            return 0;
        }
        int ans ;
        ans = Math.max(nums[index],recursion(index + 1,nums) + nums[index]);
        return ans;
    }

    // dp
    public int dp(int []nums){
        int len = nums.length;
        int  [] dp = new int[len + 1];
        dp[len] = 0;
        int ans = Integer.MIN_VALUE;
        for(int index = len - 1;index >= 0;index--){
            dp[index] = Math.max(dp[index + 1] + nums[index],nums[index]);
            ans =Math.max(ans,dp[index]);
        }
        return ans;
    }
}
